package 链表;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 * <p>
 * 示例1:
 * 输入：[1, 2, 3, 3, 2, 1]
 * 输出：[1, 2, 3]
 * <p>
 * 示例2:
 * 输入：[1, 1, 1, 1, 2]
 * 输出：[1, 2]
 * <p>
 * 提示：
 * 链表长度在[0, 20000]范围内。
 * 链表元素在[0, 20000]范围内。
 * <p>
 * 进阶：
 * 如果不得使用临时缓冲区，该怎么解决？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
 */
public class 面试题_02_01_移除重复节点 {
    public static void main(String[] args) {
        ListNode result = removeDuplicateNodes2(new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(3,new ListNode(2,new ListNode(1,null)))))));
        System.out.println(result);
    }
    public static ListNode removeDuplicateNodes(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode newNode = new ListNode(-1);
        ListNode cur = newNode;

        while (head != null) {
            if (!list.contains(head.val)) {
                cur.next = new ListNode(head.val,null);
                cur = cur.next;
                list.add(head.val);
            }
            head = head.next;
        }
        return newNode.next;
    }

    public static ListNode removeDuplicateNodes2(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while (cur.next != null) {
            if (!list.contains(head.val)) {
                cur = cur.next;
                list.add(head.val);
            }else {
                cur.next = cur.next.next;
            }
        }
        return head;
    }

    public ListNode removeDuplicateNodes1(ListNode head) {
        if (head == null) {
            return head;
        }
        Set<Integer> occurred = new HashSet<Integer>();
        occurred.add(head.val);
        ListNode pos = head;
        // 枚举前驱节点
        while (pos.next != null) {
            // 当前待删除节点
            ListNode cur = pos.next;
            if (occurred.add(cur.val)) {
                pos = pos.next;
            } else {
                pos.next = pos.next.next;
            }
        }
        pos.next = null;
        return head;
    }

}
